{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #前 K 个高频元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #divide-and-conquer #bucket-sort #counting #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #分治 #桶排序 #计数 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: topKFrequent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前 K 个高频元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code> 和一个整数 <code>k</code>&nbsp;，请返回其中出现频率前 <code>k</code> 高的元素。可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2\n",
    "<strong>输出: </strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [1], k = 1\n",
    "<strong>输出: </strong>[1]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>k</code> 的取值范围是 <code>[1, 数组中不相同的元素的个数]</code></li>\n",
    "\t<li>题目数据保证答案唯一，换句话说，数组中前 <code>k</code> 个高频元素的集合是唯一的</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>所设计算法的时间复杂度 <strong>必须</strong> 优于 <code>O(n log n)</code> ，其中 <code>n</code><em>&nbsp;</em>是数组大小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 347&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/top-k-frequent-elements/\">https://leetcode-cn.com/problems/top-k-frequent-elements/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [g5c51o](https://leetcode.cn/problems/g5c51o/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [g5c51o](https://leetcode.cn/problems/g5c51o/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        m = []\n",
    "        for num, count in c.items():\n",
    "            heappush(m, (count, num))\n",
    "        return [t for _, t in heapq.nlargest(k, m)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        ans = []\n",
    "        h = [(-v, k) for k, v in cnt.items()]\n",
    "        heapify(h)\n",
    "        for _ in range(k):\n",
    "            ans.append(heappop(h)[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        h = []\n",
    "        for ky, v in cnt.items():\n",
    "            heappush(h, (v, ky))\n",
    "            # print(h)\n",
    "            if len(h) > k:\n",
    "                heappop(h)\n",
    "            # print(h)\n",
    "        return [x for _, x in h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        mydict={}\n",
    "        for i in nums:\n",
    "            if i not in mydict:\n",
    "                mydict[i]=1\n",
    "            else:\n",
    "                mydict[i]+=1\n",
    "        l=sorted(mydict.items(),key=lambda x:x[1])\n",
    "        ret=[]\n",
    "        for i in range(k):\n",
    "            ret.append(l[len(l)-i-1][0])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = collections.defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            dic[num] += 1\n",
    "\n",
    "        stack1, stack2 = [], []\n",
    "        for key, v in dic.items():\n",
    "            while stack1 and v < dic[stack1[-1]]:\n",
    "                stack2.append(stack1.pop())\n",
    "            stack1.append(key)\n",
    "            while stack2:\n",
    "                stack1.append(stack2.pop())\n",
    "        \n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            res.append(stack1.pop())\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        hashmap = {}\n",
    "        for n in nums:\n",
    "            if n not in hashmap: hashmap[n] = 1\n",
    "            else: hashmap[n] += 1\n",
    "        \n",
    "        keys = sorted(list(hashmap.keys()), key=lambda k: hashmap[k])\n",
    "        return keys[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        # d = {}\n",
    "        # for v in nums:\n",
    "        #     if v in d:\n",
    "        #         d[v] += 1\n",
    "        #     else:\n",
    "        #         d[v] = 1\n",
    "        # res = sorted(d.items(), key = lambda x: x[1], reverse = True)\n",
    "        # return [res[i][0] for i in range(k)]\n",
    "        load = collections.Counter(nums)\n",
    "        res = []\n",
    "        for v, cnt in load.items():\n",
    "            if len(res) == k:\n",
    "                if cnt > res[0][0]:\n",
    "                    heapq.heappop(res)\n",
    "                    heapq.heappush(res, (cnt, v))\n",
    "            else:\n",
    "                heapq.heappush(res, (cnt, v))\n",
    "        return [v[1] for v in res]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            if nums[i] not in dic:\n",
    "                dic[nums[i]] = 1\n",
    "            else:\n",
    "                dic[nums[i]] += 1\n",
    "        \n",
    "        res = []\n",
    "        while k > 0:\n",
    "            tmp = 0\n",
    "            for num in dic:\n",
    "                if dic[num] > tmp:\n",
    "                    tmp = dic[num]\n",
    "                    cur = num\n",
    "            dic[cur] = -1\n",
    "            res.append(cur)\n",
    "            k -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [sorted(Counter(nums).items(), key=lambda x: x[1], reverse=True)[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        q=collections.Counter(nums)\n",
    "        q=[i for i in zip(q.keys(),q.values())]\n",
    "        q.sort(key=lambda x:x[1])\n",
    "        return [item[0] for item in q[-k:]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        hp = []\n",
    "        for num,freq in cnt.items():\n",
    "            heappush(hp,(freq,num))\n",
    "            if len(hp)>k:\n",
    "                heappop(hp)\n",
    "        return [v[1] for v in hp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:dic[num] = dic.get(num, 0)+1\n",
    "        heap = [(value, key) for key, value in dic.items()]\n",
    "        heapify(heap)\n",
    "        return [i[1] for i in nlargest(k, heap)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(nums)\n",
    "        minHeap = []\n",
    "\n",
    "        for x, f in num_freq.items():\n",
    "            if len(minHeap) == k:\n",
    "                if minHeap[0][0] < f:\n",
    "                    heapq.heappop(minHeap)\n",
    "                    heapq.heappush(minHeap, (f, x))\n",
    "            else:\n",
    "                heapq.heappush(minHeap, (f, x))\n",
    "        \n",
    "        res = []\n",
    "        while minHeap:\n",
    "            f, x = heapq.heappop(minHeap)\n",
    "            res.append(x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(nums)\n",
    "        min_heap = []\n",
    "\n",
    "        for x, f in num_freq.items():\n",
    "            if len(min_heap) == k:\n",
    "                if min_heap[0][0] < f:\n",
    "                    heapq.heappushpop(min_heap, (f,x))\n",
    "            else:\n",
    "                heapq.heappush(min_heap, (f,x))\n",
    "\n",
    "        res = []\n",
    "        while min_heap:\n",
    "            f,x = heapq.heappop(min_heap)\n",
    "            res.append(x)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        table = {}\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            if i in table.keys():\n",
    "                table[i] += 1\n",
    "            else:\n",
    "                table[i] = 1\n",
    "\n",
    "        table_order = sorted(table.items(), key=lambda x:x[1], reverse=True)\n",
    "        \n",
    "        for i in range(k):\n",
    "            res.append(table_order[i][0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_map = {}\n",
    "        for n in nums:\n",
    "            num_map[n] = num_map.get(n, 0) + 1\n",
    "\n",
    "        count_list = list(num_map.values())\n",
    "        count_list.sort(reverse=True)\n",
    "        ans = []\n",
    "        for n in range(k):\n",
    "            for key, value in num_map.items():\n",
    "                if value == count_list[n]:\n",
    "                    num_map[key] = -1\n",
    "                    ans.append(key)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "#       count=Counter(nums)\n",
    "#       a=[]\n",
    "#       ans=[]\n",
    "#       for v,c in count.items():\n",
    "#          if len(a)<k:\n",
    "#             a.append([c,v])\n",
    "#             if len(a)==k:\n",
    "#                heapq.heapify(a)\n",
    "#          else:\n",
    "#             heapq.heappushpop(a,[c,v])\n",
    "#       for vc in a:\n",
    "#          ans.append(vc[1])\n",
    "#       return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "#         d=defaultdict(int)\n",
    "#         ans=[]\n",
    "#         for num in nums:\n",
    "#             d[num]+=1\n",
    "        \n",
    "#         t=[[] for _ in range(10**5)]\n",
    "#         for key in d.keys():\n",
    "#             t[d[key]].append(key)\n",
    "#         c=0\n",
    "#         for i in range(len(t)-1,-1,-1):\n",
    "#             if len(t[i])!=0:\n",
    "#                 for j in range(len(t[i])):\n",
    "#                     ans.append(t[i][j])\n",
    "#                     c+=1\n",
    "#                     if c==k:\n",
    "#                         return ans\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        count=Counter(nums)\n",
    "        nums=list(count.keys())\n",
    "        nums.sort(key=lambda x:count[x],reverse=True)\n",
    "        ans=[]\n",
    "        c=0\n",
    "        for num in nums:\n",
    "            ans.append(num)\n",
    "            c+=1\n",
    "            if c==k:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hp\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        count = collections.Counter(nums)\n",
    "        stack = []\n",
    "        for x,f in count.items():\n",
    "            if len(stack)<k:\n",
    "                hp.heappush(stack,(f,x))\n",
    "            else:\n",
    "                if f>stack[0][0]:\n",
    "                    hp.heappush(stack,(f,x))\n",
    "                    hp.heappop(stack)\n",
    "        res = []\n",
    "        for item in stack:\n",
    "            res.append(item[1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        c = Counter(nums)\n",
    "        return [x[0] for x in c.most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k: int) :\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=1\n",
    "        heap=[]\n",
    "        for t in dic.items():\n",
    "            heapq.heappush(heap,(t[1],t[0]))\n",
    "            if len(heap)>k:\n",
    "                heapq.heappop(heap)\n",
    "        return [p[1] for p in heap ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        heapq.heapify(heap)\n",
    "        mp = {}\n",
    "        for num in nums:\n",
    "            if num not in mp:\n",
    "                mp[num] = 1\n",
    "            else:\n",
    "                mp[num] += 1\n",
    "        for num, freq in mp.items():\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, (freq, num))\n",
    "            else:\n",
    "                if freq > heap[0][0]:\n",
    "                    heapq.heappush(heap, (freq, num))\n",
    "                    heapq.heappop(heap)\n",
    "        return [n for _, n in  heap]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(nums)\n",
    "\n",
    "        minHeap = []\n",
    "\n",
    "        for x, f in num_freq.items():\n",
    "            if len(minHeap) == k:\n",
    "                if minHeap[0][0] < f:\n",
    "                    heapq.heappop(minHeap)\n",
    "                    heapq.heappush(minHeap, (f,x))\n",
    "            else:\n",
    "                heapq.heappush(minHeap, (f,x))\n",
    "\n",
    "        res = []\n",
    "        while minHeap:\n",
    "            f,x = heapq.heappop(minHeap)\n",
    "            res.append(x)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = defaultdict(int)\n",
    "        for n in nums:\n",
    "            counter[n] += 1\n",
    "        ans = []\n",
    "        while k > 0:\n",
    "            max_count = 0\n",
    "            max_key = 0\n",
    "            for key, value in counter.items():\n",
    "                if value > max_count:\n",
    "                    max_key = key\n",
    "                    max_count = value\n",
    "            counter[max_key] = 0\n",
    "            ans.append(max_key)\n",
    "            k -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        return [v[0] for v in cnt.most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = dict()\n",
    "        for num in nums:\n",
    "            if num in dic:\n",
    "                dic[num] += 1\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        heap = []\n",
    "        for key,value in dic.items():\n",
    "            heapq.heappush(heap, (value, key))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        return [item[1] for item in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = collections.Counter(nums)\n",
    "        heap = []\n",
    "        for key, val in counter.items():\n",
    "            if len(heap) >= k:\n",
    "                if heap[0][0] < val:\n",
    "                    heapq.heapreplace(heap, (val, key))\n",
    "            else:\n",
    "                heapq.heappush(heap, (val, key))\n",
    "        return [item[1] for item in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        freq = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in freq:\n",
    "                freq[nums[i]] += 1\n",
    "            else:\n",
    "                freq[nums[i]] = 1\n",
    "        freq_sorted = sorted(freq.items(), key=lambda x: x[1], reverse=True)\n",
    "        result = []\n",
    "        for key, val in freq_sorted:\n",
    "            if len(result) < k:\n",
    "                result.append(key)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        d=Counter(nums)\n",
    "        hp=[(v,k) for k,v in d.items()]\n",
    "        heapq.heapify(hp)\n",
    "        return [row[1] for row in heapq.nlargest(k,hp)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(nums)\n",
    "        res = []\n",
    "        for i,j in num_freq.items():\n",
    "            if len(res)==k:\n",
    "                if j>res[0][0]:\n",
    "                    heapq.heappop(res)\n",
    "                    heapq.heappush(res,(j,i))\n",
    "            else:\n",
    "                heapq.heappush(res,(j,i))\n",
    "        res0=[]\n",
    "        while res:\n",
    "            for i in res:\n",
    "                res0.append(i[1])\n",
    "            return res0\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        arr=list(cnt.items())\n",
    "        arr.sort(reverse=True,key= lambda x:x[1])\n",
    "        return [i for i,x in arr[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        h = []\n",
    "        for key, v in cnt.items():\n",
    "            if len(h) < k:\n",
    "                heappush(h, (v, key))\n",
    "            elif v > h[0][0]:\n",
    "                heapreplace(h, (v, key))\n",
    "        \n",
    "        ans = [0] * k\n",
    "        for i in range(k-1, -1, -1):\n",
    "            ans[i] = heappop(h)[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        nums_dic = collections.Counter(nums)\n",
    "        print(nums_dic)\n",
    "        T = sorted(nums_dic.items(),key = lambda x:x[-1],reverse=True)\n",
    "        for i,(key,v) in zip(range(k),T):\n",
    "            # print('key',nums_dic.items())\n",
    "            res.append(key)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        heap = []\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num in dic:\n",
    "                dic[num] += 1\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        for key, val in dic.items():\n",
    "            heapq.heappush(heap, (val, key))\n",
    "        while len(heap) > k:\n",
    "            heapq.heappop(heap)\n",
    "        print(heap)\n",
    "        for i in heap:\n",
    "            ans.append(i[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        s_dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in s_dic.keys():\n",
    "                s_dic[nums[i]] =1\n",
    "            else:\n",
    "                s_dic[nums[i]] +=1\n",
    "        res_t = sorted(s_dic.items(),key=lambda x:x[-1],reverse=True)\n",
    "        for i in range(k):\n",
    "            res.append(res_t[i][0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        temp=Counter(nums)\n",
    "        temp=temp.most_common(k)\n",
    "        result=[]\n",
    "\n",
    "        for i in temp:\n",
    "            result.append(i[0])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_dict = {}\n",
    "        for num in nums:\n",
    "            if num not in num_dict:\n",
    "                num_dict[num] = 0\n",
    "            num_dict[num] += 1\n",
    "\n",
    "        res = []\n",
    "        left_res = []\n",
    "        for num in num_dict:\n",
    "            if len(res) < k:\n",
    "                res.append((num_dict[num], num))\n",
    "            else:\n",
    "                left_res.append((num_dict[num], num))\n",
    "\n",
    "        if len(res) < k:\n",
    "            return [_[1] for _ in res]\n",
    "\n",
    "        heapq.heapify(res)\n",
    "        for r in left_res:\n",
    "            if res[0][0] < r[0]:\n",
    "                heapq.heappop(res)\n",
    "                heapq.heappush(res, r)\n",
    "\n",
    "        return [_[1] for _ in res]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        arr=list(cnt.items())\n",
    "        arr.sort(reverse=True,key= lambda x:x[1])\n",
    "        return [i for i,x in arr[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        #def kthelement(nums,k):\n",
    "\n",
    "        hash={}\n",
    "        for i in nums:\n",
    "            if i not in hash:\n",
    "                hash[i]=1\n",
    "            else:\n",
    "                hash[i]+=1\n",
    "        count=[(i,hash[i]) for i,hash[i] in hash.items()]\n",
    "        # def partition(left,right):#将下标为mindex前的元素排列好，包括mindex\n",
    "        #     index=left\n",
    "        #     pivot=count[left]\n",
    "        #     while left<right:   \n",
    "        #         while count[right][1]<=pivot[1] and left<right:\n",
    "        #             right-=1\n",
    "        #         count[right]=count[left]\n",
    "        #         while count[left][1]>=pivot[1] and left<right:\n",
    "        #             left+=1\n",
    "        #         count[left]=count[right]\n",
    "        #     count[right]=pivot\n",
    "        #     return index\n",
    "        def partition(left, right):\n",
    "            pivot = count[left]  # Choose the first element as the pivot\n",
    "            i = left + 1\n",
    "            j = right\n",
    "\n",
    "            while True:\n",
    "                while i <= j and count[i][1] >= pivot[1]:\n",
    "                    i += 1\n",
    "                while i <= j and count[j][1] <= pivot[1]:\n",
    "                    j -= 1\n",
    "                if i <= j:\n",
    "                    count[i], count[j] = count[j], count[i]  # Swap elements\n",
    "                else:\n",
    "                    break\n",
    "            count[left], count[j] = count[j], count[left]  # Place the pivot in the correct position\n",
    "            return j\n",
    "        def qsort(left,right,k):#将前k个元素排列好\n",
    "            mindex=partition(left,right) \n",
    "            if mindex==k-1:\n",
    "                return\n",
    "            elif mindex<k-1:\n",
    "                qsort(mindex+1,right,k)\n",
    "            else:\n",
    "                qsort(left,mindex-1,k)\n",
    "            return \n",
    "           \n",
    "        qsort(0,len(count)-1,k)\n",
    "        #print(count)\n",
    "        print(count)\n",
    "        return [i[0] for i in count[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        arr = []\n",
    "        exsit = []\n",
    "        for c in nums:\n",
    "            if  c not in exsit:\n",
    "                arr.append([c, nums.count(c)])\n",
    "                exsit.append(c)\n",
    "\n",
    "        arr.sort(key=lambda x:-x[1])\n",
    "\n",
    "        res = [x[0] for x in arr][:k]\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            dic[num] = dic.get(num, 0) + 1\n",
    "\n",
    "        curlen = 0\n",
    "        val = list(dic.items())\n",
    "        val.sort(key = lambda x:x[1], reverse = True)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(val[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dict1 = {}\n",
    "\n",
    "        for item in nums:\n",
    "            if(item not in dict1):\n",
    "                dict1[item] = 0\n",
    "            dict1[item] = dict1[item] + 1\n",
    "\n",
    "        res = []\n",
    "        for item in dict1:\n",
    "            res.append([item,dict1[item]])\n",
    "        \n",
    "        return [ item1[0] for item1 in sorted(res, key=lambda item: -item[1])[:k]  ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        from collections import Counter\n",
    "        dic = Counter(nums)\n",
    "        a = sorted(dic.items(), key=lambda s: (-s[1]))\n",
    "        answer= []\n",
    "        for value in a:\n",
    "            if len(answer) < k:\n",
    "                answer.append(value[0])\n",
    "            else:\n",
    "                break\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        hp = []\n",
    "        for key, v in cnt.items():\n",
    "            heapq.heappush(hp, (v, key))\n",
    "            while len(hp) > k:\n",
    "                heapq.heappop(hp)\n",
    "        \n",
    "        return [x[1] for x in hp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "         counter=dict(collections.Counter(nums))\n",
    "         new_counter=sorted(counter.items(),key=lambda x: x[1],reverse=True)\n",
    "         return [num[0] for num in new_counter][:k]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_freq = collections.Counter(nums)\n",
    "        minHeap = []\n",
    "\n",
    "        for x, f in num_freq.items():\n",
    "            if len(minHeap) == k:\n",
    "                if minHeap[0][0] < f:\n",
    "                    heapq.heappop(minHeap)\n",
    "                    heapq.heappush(minHeap, (f, x))\n",
    "            else:\n",
    "                heapq.heappush(minHeap, (f, x))\n",
    "        \n",
    "        res = []\n",
    "        while minHeap:\n",
    "            f, x = heapq.heappop(minHeap)\n",
    "            res.append(x)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        digits = dict()\n",
    "        for num in nums:\n",
    "            digits[num] = digits.get(num, 0) + 1\n",
    "        for key, value in digits.items():\n",
    "            res.append([key, value])\n",
    "        res.sort(key=lambda x:-x[1])\n",
    "        return [res[i][0] for i in range(k)]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = Counter(nums)\n",
    "        lst = sorted((i for i in cnt.keys()), key=lambda x: cnt[x], reverse=True)\n",
    "        return lst[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        return [i[0] for i in Counter(nums).most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_ct_map = {}\n",
    "        for num in nums:\n",
    "            if not num in num_ct_map:\n",
    "                num_ct_map[num] = 1\n",
    "            else:\n",
    "                num_ct_map[num] += 1\n",
    "        num_ct_lst = sorted([[num,num_ct_map[num]] for num in num_ct_map],key=lambda x:x[1],reverse=True)\n",
    "        return [item[0] for item in num_ct_lst[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d[num] += 1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "        \n",
    "        def compare(a, b):\n",
    "            return d[b] - d[a]\n",
    "        \n",
    "        return sorted(d.keys(), key=functools.cmp_to_key(compare))[:k]\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = collections.Counter(nums)\n",
    "        heap = []\n",
    "        for n, freq in counter.items():\n",
    "            heapq.heappush(heap, [freq, n])\n",
    "            while len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        return [x[1] for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = collections.Counter(nums)\n",
    "        heap = []\n",
    "        for n, freq in counter.items():\n",
    "            heapq.heappush(heap, [freq, n])\n",
    "            while len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        \n",
    "        return [x[1] for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cnt = {}\n",
    "        for i in nums:\n",
    "            cnt[i] = cnt.get(i,0)+1\n",
    "        cnt = sorted(cnt.items(),key=lambda x:x[1],reverse=True)\n",
    "        res = []\n",
    "        print(cnt)\n",
    "        for key in cnt:\n",
    "            res.append(key[0])\n",
    "        return res[:k]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        cdict={}\n",
    "        for num in nums:\n",
    "            if num in cdict:\n",
    "                cdict[num]+=1\n",
    "            else:\n",
    "                cdict[num]=1\n",
    "        s=sorted(cdict.items(),key=lambda x:x[1],reverse=True)\n",
    "        sorted_s=[t[0] for t in s]\n",
    "        return sorted_s[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        hash = dict(Counter(nums))\n",
    "        hashsort = sorted(hash, key = lambda x : hash[x], reverse=True)\n",
    "        return hashsort[:k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, words: List[str], k: int) -> List[str]:\n",
    "        dit = {}\n",
    "        data = []\n",
    "        for i in words:\n",
    "            if dit.get(i) == None:\n",
    "                dit[i] = 1\n",
    "            else:\n",
    "                dit[i]+=1\n",
    "        dit = sorted(dit.items(),key = lambda x : (-x[1]))\n",
    "        print(dit)\n",
    "        for i in range(k):\n",
    "            data.append(dit[i][0])\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        counter = defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            counter[num] += 1\n",
    "        \n",
    "        items = list(counter.keys())\n",
    "        return sorted(items, key=lambda x: counter[x])[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        mydict = {}\n",
    "        for each in nums:\n",
    "            if each in mydict:\n",
    "                mydict[each] +=1\n",
    "            else:\n",
    "                mydict[each] = 1\n",
    "        mydict = sorted(mydict.items(),key=lambda x:x[1],reverse=True)#按照值进行排序\n",
    "\n",
    "        res = []\n",
    "        for i,each in enumerate(mydict):\n",
    "            if i < k:\n",
    "                res.append(each[0])\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        import collections\n",
    "        counter = collections.Counter(nums)\n",
    "        counter = dict(sorted(counter.items(), key=lambda item: item[1], reverse=True))\n",
    "        result = []\n",
    "        i = 0\n",
    "        for k_, v in counter.items():\n",
    "            if i == k:\n",
    "                break\n",
    "            i += 1\n",
    "            result.append(k_)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        for x in nums:\n",
    "            d[x] += 1\n",
    "        new_d = sorted(d.items(), key= lambda x: -x[1])\n",
    "        \n",
    "        ans = [item[0] for item in new_d[:k]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num not in dic:\n",
    "                dic[num] = 1\n",
    "            else:\n",
    "                dic[num] += 1\n",
    "        nums = list(zip(dic.keys(), dic.values()))\n",
    "        nums.sort(key=lambda x: -x[1])\n",
    "        return [nums[i][0] for i in range(k)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        hmap = defaultdict(int)\n",
    "\n",
    "        for num in nums:\n",
    "            hmap[num] += 1\n",
    "        \n",
    "        sorted_l = sorted(hmap.items(),key=lambda x : x[1],reverse=True)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(sorted_l[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        #可以按任意顺序，说明只要找到第K频，无需对前后排序\n",
    "        #第k频，那一定要统计频率\n",
    "        #考虑 计数排序，本质上用空间换时间，统计好也就算好了一切\n",
    "        dict_value={}\n",
    "        for num in nums:\n",
    "            if num not in dict_value:\n",
    "                dict_value[num]= 1 \n",
    "            else:\n",
    "                dict_value[num]=dict_value[num]+1\n",
    "        nums_value=[]\n",
    "        max_num=0\n",
    "        min_num=-1\n",
    "        for v in dict_value:\n",
    "            nums_value.append([v,dict_value[v]])\n",
    "            if dict_value[v]>=max_num:\n",
    "                max_num=dict_value[v]\n",
    "            if min_num==-1 or dict_value[v]<min_num:\n",
    "                min_num=dict_value[v]\n",
    "        #桶\n",
    "        c=[[] for i in range(max_num-min_num+1)]\n",
    "        for item in nums_value:\n",
    "            c[item[1]-min_num].append(item[0])\n",
    "        ret=[]\n",
    "        for i in range(len(c)):\n",
    "            if c[len(c)-1-i]!=[]:\n",
    "                ret=ret+c[len(c)-1-i]\n",
    "            if len(ret)>=k:return ret\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "\n",
    "    # 使用 Counter 计算元素出现的频率\n",
    "        freqs = Counter(nums)\n",
    "    \n",
    "    # 对字典中的元素按照出现频率降序排序\n",
    "        sorted_freqs = sorted(freqs.items(), key=lambda x: x[1], reverse=True)\n",
    "    \n",
    "    # 提取前 k 高频元素并返回\n",
    "        return [item[0] for item in sorted_freqs[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quick_sort(self,nums,k):\n",
    "        #返回的是前k高，而不是第k高\n",
    "        big=[]\n",
    "        small=[]\n",
    "        equal=[]\n",
    "        pivot=random.choice(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i][1]>pivot[1]:\n",
    "                big.append(nums[i])\n",
    "            elif nums[i][1]==pivot[1]:\n",
    "                equal.append(nums[i])\n",
    "            else:\n",
    "                small.append(nums[i])\n",
    "        #print(pivot,k,big,equal,small)\n",
    "        if len(big)>=k:\n",
    "            return self.quick_sort(big,k)\n",
    "        else:\n",
    "            if  len(big)+len(equal)>=k:\n",
    "                return [x[0] for x in (big+equal)]\n",
    "            else:\n",
    "                return [x[0] for x in (big+equal)]+self.quick_sort(small,k-len(big)-len(equal))\n",
    "\n",
    "\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        #可以按任意顺序，说明只要找到第K频，无需对前后排序\n",
    "        #第k频，那一定要统计频率=>有点像计数排序，要先建立map[value]=v_num,然后就是经典的k_th选择问题\n",
    "\n",
    "        dict_value={}\n",
    "        for num in nums:\n",
    "            if num not in dict_value:\n",
    "                dict_value[num]= 1 \n",
    "            else:\n",
    "                dict_value[num]=dict_value[num]+1\n",
    "        nums_value=[]\n",
    "        for v in dict_value:\n",
    "            nums_value.append([v,dict_value[v]])\n",
    "        return self.quick_sort(nums_value,k)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            if nums[i] in dic:\n",
    "                dic[nums[i]] += 1\n",
    "            else:\n",
    "                dic[nums[i]] = 1\n",
    "\n",
    "        queue = []\n",
    "\n",
    "        for freq, val in dic.items():\n",
    "            heapq.heappush(queue, [val, freq])\n",
    "            if len(queue) > k:\n",
    "                heapq.heappop(queue)\n",
    "        \n",
    "        result = []\n",
    "        for i in range(k-1, -1, -1):\n",
    "            result.append(heapq.heappop(queue)[1])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_dict={}\n",
    "        for num in nums:\n",
    "            if num in num_dict:\n",
    "                num_dict[num]+=1\n",
    "            else:\n",
    "                num_dict[num]=1\n",
    "        num_dict=sorted(num_dict.items(),key=lambda x:x[1],reverse=True)\n",
    "        res=[]\n",
    "        for i,num in enumerate(num_dict):\n",
    "            if i<k:\n",
    "                res.append(num[0])\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        record = Counter(nums)\n",
    "        temp = sorted(record.items(), key = lambda x: -x[1])\n",
    "        res = [x[0] for x in temp[:k]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        from collections import Counter\n",
    "        num_freq = collections.Counter(nums)\n",
    "        minHeap = []\n",
    "\n",
    "        for x,f in num_freq.items():\n",
    "            if len(minHeap) == k:\n",
    "                if minHeap[0][0]<f:\n",
    "                    heapq.heappop(minHeap)\n",
    "                    heapq.heappush(minHeap,(f,x))\n",
    "            else:\n",
    "                heapq.heappush(minHeap,(f,x))\n",
    "\n",
    "        res = []\n",
    "        while minHeap:\n",
    "            f,x = heappop(minHeap)\n",
    "            res.append(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        hash_table = {}\n",
    "        for num in nums:\n",
    "            if num not in hash_table:\n",
    "                hash_table[num] = 1\n",
    "            else:\n",
    "                hash_table[num] += 1\n",
    "        keys, values = hash_table.keys(), hash_table.values()\n",
    "        sorted_index = [i for i, _ in sorted(enumerate(values), key=lambda x: x[1], reverse=True)]\n",
    "        res = []\n",
    "\n",
    "        for index in sorted_index:\n",
    "            res.append(list(keys)[index])\n",
    "            if len(res) == k:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 出现频率最高的前k个元素\n",
    "      \n",
    "        def quick_sort(nums,start, end,k):\n",
    "            # if start >= end:\n",
    "            #     return\n",
    "            temp = nums[start][1]\n",
    "            i = start \n",
    "            j = end\n",
    "            while i < j:\n",
    "              \n",
    "                while nums[j][1] <= temp and j > i:\n",
    "                    j = j - 1\n",
    "\n",
    "                while nums[i][1] >= temp and i < j:\n",
    "                    i = i + 1\n",
    "               \n",
    "                if i != j:\n",
    "                    x = nums[i]\n",
    "                    nums[i] = nums[j]\n",
    "                    nums[j] = x\n",
    "\n",
    "        \n",
    "            if i == j:\n",
    "                x = nums[start]\n",
    "                nums[start] = nums[i]\n",
    "                nums[i] = x\n",
    "            idx = i\n",
    "            if k == i - start + 1:\n",
    "                for t in range(start,i+1):\n",
    "                    \n",
    "                    self.res.append(nums[t][0])  \n",
    "            elif  k < i - start + 1:\n",
    "                quick_sort(nums,start, i-1,k)\n",
    "           \n",
    "\n",
    "            else:\n",
    "            \n",
    "                for t in range(start,i+1):\n",
    "                    self.res.append(nums[t][0])  \n",
    "                quick_sort(nums,i + 1, end,k-(i-start+1))\n",
    "\n",
    "          \n",
    "       \n",
    "        num_freq = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in num_freq.keys():\n",
    "                num_freq[nums[i]] = 1\n",
    "            else:\n",
    "                num_freq[nums[i]] = num_freq[nums[i]] + 1\n",
    "        \n",
    "        xfs = list(num_freq.items())\n",
    "        # print(xfs)\n",
    "        \n",
    "        self.res = []\n",
    "        length = len(xfs)\n",
    "        quick_sort(xfs,0,length-1,k)\n",
    "        print(xfs)\n",
    "        \n",
    "        return self.res\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "             \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        # 出现频率最高的前k个元素\n",
    "      \n",
    "        def quick_sort(nums,start, end,k):\n",
    "            # if start >= end:\n",
    "            #     return\n",
    "            temp = nums[start][1]\n",
    "            i = start \n",
    "            j = end\n",
    "            while i < j:\n",
    "              \n",
    "                while nums[j][1] <= temp and j > i:\n",
    "                    j = j - 1\n",
    "\n",
    "                while nums[i][1] >= temp and i < j:\n",
    "                    i = i + 1\n",
    "               \n",
    "                if i != j:\n",
    "                    x = nums[i]\n",
    "                    nums[i] = nums[j]\n",
    "                    nums[j] = x\n",
    "\n",
    "        \n",
    "            if i == j:\n",
    "                x = nums[start]\n",
    "                nums[start] = nums[i]\n",
    "                nums[i] = x\n",
    "            idx = i\n",
    "            if k == i - start + 1:\n",
    "                for t in range(start,i+1):\n",
    "                    \n",
    "                    self.res.append(nums[t][0])  \n",
    "            elif  k < i - start + 1:\n",
    "                quick_sort(nums,start, i-1,k)\n",
    "           \n",
    "\n",
    "            else:\n",
    "            \n",
    "                for t in range(start,i+1):\n",
    "                    self.res.append(nums[t][0])  \n",
    "                quick_sort(nums,i + 1, end,k-(i-start+1))\n",
    "\n",
    "          \n",
    "       \n",
    "        num_freq = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in num_freq.keys():\n",
    "                num_freq[nums[i]] = 1\n",
    "            else:\n",
    "                num_freq[nums[i]] = num_freq[nums[i]] + 1\n",
    "        \n",
    "        xfs = list(num_freq.items())\n",
    "        # print(xfs)\n",
    "        \n",
    "        self.res = []\n",
    "        length = len(xfs)\n",
    "        quick_sort(xfs,0,length-1,k)\n",
    "       \n",
    "        \n",
    "        return self.res\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "             \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class quickSort:\n",
    "    def quickSort(self, nums, left, right, k):\n",
    "        \"\"\"对nums快排，使得前k个元素 >= 后n - k个元素\"\"\"\n",
    "        mid = self.randomPartition(nums, left, right)\n",
    "        if mid == k - 1:\n",
    "            return nums[mid]\n",
    "        elif mid < k - 1:\n",
    "            return self.quickSort(nums, mid + 1, right, k)\n",
    "        else:\n",
    "            return self.quickSort(nums, left, mid - 1, k)\n",
    "\n",
    "    def randomPartition(self, nums, left, right):\n",
    "        idx = random.randint(left, right)\n",
    "        nums[idx], nums[left] = nums[left], nums[idx]\n",
    "        return self.partition(nums, left, right)\n",
    "\n",
    "    def partition(self, nums, left, right):\n",
    "        \"\"\"将nums分为小于pivot的部份和大于pivot的部份\"\"\"\n",
    "        pivot = nums[left]\n",
    "        l, r = left, right\n",
    "        \n",
    "        while l < r:\n",
    "            while l < r and nums[r] <= pivot:\n",
    "                r -= 1\n",
    "            nums[l] = nums[r]\n",
    "            while l < r and nums[l] >= pivot:\n",
    "                l += 1\n",
    "            nums[r] = nums[l]\n",
    "        nums[l] = pivot\n",
    "\n",
    "        return l\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        思路1：大小为k的堆\n",
    "        思路2：快速排序\n",
    "        \"\"\"\n",
    "\n",
    "        numCount = collections.defaultdict(int)\n",
    "        for n in nums:\n",
    "            numCount[n] += 1\n",
    "        \n",
    "        count = []\n",
    "        for key, v in numCount.items():\n",
    "            count.append(v)\n",
    "\n",
    "        quick = quickSort()\n",
    "\n",
    "        thres = quick.quickSort(count, 0, len(count) - 1, k)\n",
    "\n",
    "        print(thres, count, numCount)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for key, v in numCount.items():\n",
    "            if len(res) == k:\n",
    "                break\n",
    "            if v >= thres:\n",
    "                res.append(key)\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
